//package test;
//
//class TreeNode {
//    int val;
//    int bf;
//    TreeNode left;
//    TreeNode right;
//    TreeNode parent;
//
//    public TreeNode(int val) {
//        this.val = val;
//    }
//}
//
//public class AVLTree {
//    public TreeNode root;
//
//    public boolean insert(int val) {
//        TreeNode node = new TreeNode(val);
//        if (root == null) {
//            root = node;
//            return true;
//        }
//
//        TreeNode pre = null;
//        TreeNode cur = root;
//        while (cur != null) {
//            if (cur.val < val) {
//                pre = cur;
//                cur = cur.right;
//            } else if (cur.val > val) {
//                pre = cur;
//                cur = cur.left;
//            } else {
//                return false;
//            }
//        }
//
//        if (pre.val < val) {
//            pre.right = node;
//        } else {
//            pre.left = node;
//        }
//        //插入新元素后根据平衡因子进行对树的调整
//        node.parent = pre;
//        cur = node;
//
//        //调节平衡因子
//        while (pre != null) {
//            if (cur == pre.right) {
//                pre.bf++;
//            } else {
//                pre.bf--;
//            }
//
//            if (pre.bf == 0) {
//                //刚插入就平衡，不用继续向上调整
//                break;
//            } else if (pre.bf == 1 || pre.bf == -1) {
//                //插入之后打破平衡，继续向上调整
//                cur = pre;
//                pre = cur.parent;
//            } else {
//                if (pre.bf == 2) {//右树高，左旋
//                    if (cur.bf == 1) {
//                        //左单旋
//                        rotateLeft(pre);
//                    } else {
//                        //cur.bf == -1
//                        rotateRL(pre);
//                    }
//                } else {
//                    //pre.bf == -2 左树高，需要降低左树的高度
//                    if (cur.bf == -1) {
//                        //右单旋
//                        rotateRight(pre);
//                    } else {
//                        //cur.bf == 1
//                        //左右双旋
//                        rotateLR(pre);
//                    }
//                }
//                break;
//            }
//        }
//        return true;
//    }
//
//    public void rotateRL(TreeNode pre) {
//
//    }
//
//    public void rotateLR(TreeNode pre) {
//        TreeNode subL = pre.left;
//        TreeNode subLR = subL.right;
//        int bf = subLR.bf;
//        rotateLeft(pre.left);
//        rotateRight(pre);
//        if (bf == -1) {
//            subL.bf = 0;
//            subLR.bf = 0;
//            pre.bf = 1;
//        } else {
//            subL.bf = -1;
//            subLR.bf = 0;
//            pre.bf = 0;
//        }
//    }
//
//    //左单旋
//    public void rotateLeft(TreeNode pre) {
//        TreeNode subR = pre.right;
//        TreeNode subRL = subR.left;
//
//        pre.right = subRL;
//        subR.left = pre;
//
//        if (subRL != null) {
//            subRL.parent = pre;
//        }
//
//        TreeNode pPre = pre.parent;
//        pre.parent = subR;
//
//        if (root == pPre) {
//            root = subR;
//            root.parent = null;
//        } else {
//            if (pPre.left == pre) {
//                pPre.left = subR;
//            } else {
//                pPre.right = subR;
//            }
//            subR.parent = pPre;
//        }
//        subR.bf = 0;
//        pre.bf = 0;
//    }
//
//    //右单旋
//    public void rotateRight(TreeNode pre) {
//        TreeNode subL = pre.left;
//        TreeNode subLR = subL.right;
//        pre.left = subLR;
//        subL.right = pre;
//        //没有subLR的时候
//        if (subLR != null) {
//            subLR.parent = pre;
//        }
//        TreeNode pPre = pre.parent;
//        pre.parent = subL;
//        //检查当前是不是根节点
//        if (pre == root) {
//            root = subL;
//            root.parent = null;
//        } else {
//            //不是根节点，判断这棵树是左子树还是右子树
//            if (pPre.left == pre) {
//                pPre.left = subL;
//            } else {
//                pPre.right = subL;
//            }
//            subL.parent = pPre;
//        }
//        subL.bf = 0;
//        pre.bf = 0;
//    }
//
//    public static void main(String[] args) {
//
//    }
//}
